In systems that use shared secret verification e.g. two parties may each have a secret. They want to find out whether they share the same secret or not but don't want to disclose the secret itself to each other or to a third party. Related to modern telecommunications, the invention refers to secure communication (public and/or private keys), zero-knowledge proofs, one-way (hash) functions, commitment schemes, data compression etc. Applications are among others in the field of secure group formation, e.g. in Internet encountering, in which e.g. two parties meet on the Internet. At a later instance they meet again on the Internet. The problem is how parties can verify that the other is the same party that they met previously, without having to disclose identity information. Another example is the problem which arises when e.g. two mobile devices are tapped against each other to generate a secret time stamp, which is the exact instance of time when the two devices tapped. At a later instance they want to communicate with each other. The problem then is how to verify that the other device has exactly the same time stamp without disclosing the own time stamp.
The problem to which the method according to the present invention aims to provide a solution could be stated as follows: At one point in time, place and communication means, a secret was created. The secret is shared between two or more parties. These parties could be people, machines, or both. At a different point in time, place and/or communication means, two or more parties meet, and want to verify whether the other(s) have the same shared secret. There are no trusted third parties that could be invoked. The secret may have small Shannon entropy. If the protocol/algorithm fails, the fraud has learned no more information than just that. Moreover, the method according the invention should preserve privacy optimally, no identification information should be exchanged either when the secret is created or when it is verified. Also, no third party should be needed either for authentication or verification.
In cryptography, secure multi-party computation (MPC) is a problem that was initially suggested by Andrew C. Yao in 1982 [Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164]. In that publication, the millionaire problem was introduced: Alice and Bob are two millionaires who want to find out which is richer without revealing the precise amount of their wealth. Yao proposed a solution allowing Alice and Bob to satisfy their curiosity while respecting the constraints.
Secure MPC provides solutions to various real-life problems such as distributed voting, private bidding and auctions, sharing of signature or decryption functions, private information retrieval, etc. The first large-scale and practical application of multiparty computation took place in Denmark in January 2008 [Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielsen, Jakob Pagter, Michael Schwartzbach and Tomas Toft: Multiparty Computation Goes Live, Cryptology ePrint Archive: Report 2008/068]
The prior art solution to the Millionaire's Problem is illustrated below. Two millionaires, Alice and Bob (usual in cryptography to indicate two parties, A and B) want to know which is richer, without revealing their actual wealth. To begin with, Alice and Bob need a public-key cryptographic system which is strong: in this example RSA. Alice uses RSA, and has a public key which is (79, 3337). Her private key is 1019. To keep the example simple, Alice and Bob have worked out from their Rolls-Royce collections that they are both worth somewhere in the region of 1 to 10 million. They don't want to tell each other how rich they are, but they do want to know which is richer. Alice is worth I millions, and Bob J millions. For this example we will say that Alice is worth 5 million (I=5) and Bob 6 million (J=6). We will just use the numbers 1 to 10, not the millions, although the technique is extendable to the millions.